package test3;

import java.util.ArrayList;
import java.util.List;

public class Solution4 {
    static class Trie {
        char val;
        Trie[] child;
        boolean isWord;
        public Trie() {
            child = new Trie[26];
        }
        public Trie(char val) {
            this.val = val;
            child = new Trie[26];
        }

        /** Inserts a word into the trie. */
        public void insert(String word) {
            char[] chars = word.toCharArray();
            Trie current = this;
            for (char c : chars) {
                if (current.child[c - 'a'] == null) {
                    current.child[c - 'a'] = new Trie(c);
                }
                current = current.child[c - 'a'];
            }
            current.isWord = true;
        }

        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            char[] chars = word.toCharArray();
            Trie current = this;
            for (char c : chars) {
                if (current.child[c - 'a'] == null) {
                    return false;
                }
                current = current.child[c - 'a'];
            }
            if (current.isWord) {
                return true;
            }
            return false;
        }

        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            char[] chars = prefix.toCharArray();
            Trie current = this;
            for (char c : chars) {
                if (current.child[c - 'a'] == null) {
                    return false;
                }
                current = current.child[c - 'a'];
            }
            return true;
        }

        public String getRootWord(String word) {
            StringBuilder builder = new StringBuilder();
            char[] chars = word.toCharArray();
            Trie current = this;
            for (char c : chars) {
                if (current.child[c - 'a'] == null) {
                    System.out.println(word + ":null");
                    return word;
                }
                System.out.println(word + ":" + current.child[c - 'a'].val);
                builder.append(c);
                current = current.child[c - 'a'];
                if (current.isWord) {
                    return builder.toString();
                }
            }
            return word;
        }

    }

    public static String replaceWords(List<String> roots, String sentence) {
        Trie trie = new Trie();
        for(String root: roots) {
            trie.insert(root);
        }
        String[] split = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for(String str : split) {
            sb.append(trie.getRootWord(str));
            sb.append(" ");
        }
        return sb.substring(0, sb.length()-1);

    }

    public static void main(String[] args) {
        ArrayList<String> roots = new ArrayList<>();
        roots.add("cat");
        roots.add("bat");
        roots.add("rat");
        replaceWords(roots, "the cattle was rattled by the battery");
    }

    class WordFilter {
        TrieNode trie;
        public WordFilter(String[] words) {
            trie = new TrieNode();
            for (int weight = 0; weight < words.length; ++weight) {
                String word = words[weight] + "{";
                for (int i = 0; i < word.length(); ++i) {
                    TrieNode cur = trie;
                    cur.weight = weight;
                    for (int j = i; j < 2 * word.length() - 1; ++j) {
                        int k = word.charAt(j % word.length()) - 'a';
                        if (cur.children[k] == null)
                            cur.children[k] = new TrieNode();
                        cur = cur.children[k];
                        cur.weight = weight;
                    }
                }
            }
        }
        public int f(String prefix, String suffix) {
            TrieNode cur = trie;
            for (char letter: (suffix + '{' + prefix).toCharArray()) {
                if (cur.children[letter - 'a'] == null) return -1;
                cur = cur.children[letter - 'a'];
            }
            return cur.weight;
        }
    }
    class TrieNode {
        TrieNode[] children;
        int weight;
        public TrieNode() {
            children = new TrieNode[27];
            weight = 0;
        }
    }



}
